package com.lw.leetcode.sort.b;

import java.util.TreeSet;

/**
 * Created with IntelliJ IDEA.
 * 855. 考场就座
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/30 9:58
 */
public class ExamRoom {

    private TreeSet<Integer> set = new TreeSet<>();
    private int size;

    public ExamRoom(int N) {
        this.size = N - 1;
    }

    public int seat() {
        int index = 0;
        if (set.isEmpty()) {
            set.add(0);
            return 0;
        }
        int dist = set.first();
        Integer prev = null;
        for (Integer seat : set) {
            if (prev != null) {
                int d = (seat - prev) >> 1;
                if (d > dist) {
                    dist = d;
                    index = (seat + prev) >> 1;
                }
            }
            prev = seat;
        }
        if (size - set.last() > dist) {
            index = size;
        }
        set.add(index);
        return index;
    }

    public void leave(int p) {
        set.remove(p);
    }

}
